package problems.practice;

/**
 * 1223. 掷骰子模拟
 * <p>https://leetcode.cn/problems/dice-roll-simulation/</p>
 * <p>题解参考：</p>
 * <li>https://leetcode.cn/problems/dice-roll-simulation/solution/ni-bi-dong-chao-jian-dan-dong-tai-gui-hua-fu-za-du/</li>
 * <li>https://leetcode.cn/problems/dice-roll-simulation/solution/java-2wei-dp-by-zdxiq125/</li>
 *
 * @author habitplus
 * @since 2022/10/8 19:05
 */
public class T1223 {
    static final int MOD = (int) (1e9 + 7);

    public int dieSimulator(int n, int[] rollMax) {
        // 动态规划：
        // dp[i][j] 表示掷第 i 次时，点数是 j 的序列数总和
        // dp[i][j] = sum(dp[i-1][1 ... 6]) - sum(dp[i-rollMax[j]-1][0 ... 5, 排除j])
        int m = 6;
        int[][] dp = new int[n][m];

        for (int i = 0; i < m; ++i) dp[0][i] = 1;

        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                for (int k = 0; k < m; ++k) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
                }

                if (i == rollMax[j]) {
                    dp[i][j]--;
                } else if (i > rollMax[j]) {
                    for (int k = 0; k < 6; k++) {
                        if (j != k)
                            // 需要防止出现负数的情况
                            dp[i][j] = (dp[i][j] - dp[i - rollMax[j] - 1][k] + MOD) % MOD;
                    }
                }
            }
        }

        long ret = 0L;

        for (int i = 0; i < m; ++i) {
            ret = (ret + dp[n - 1][i]) % MOD;
        }

        return (int) ret;
    }
}
